On Sun, Jul 24, 2022 at 12:48:25PM +0800, Zhang Mingli wrote: > If snaphost->suboverflowed is false then the subxcnt must be less than PGPROC_MAX_CACHED_SUBXIDS which is 64 now. > > And we won’t use hash if the xcnt is less than XIP_HASH_MIN_ELEMENTS which is 128 currently during discussion. > > So that, subxid’s hash table will never be used, right? This array will store up to TOTAL_MAX_CACHED_SUBXIDS transactions, which will typically be much greater than 64. When there isn't any overflow, subxip stores all of the subxids for all of the entries in the procarray. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com

Hi Andres, Thanks for taking a look. On Fri, Jul 15, 2022 at 01:08:57PM -0700, Andres Freund wrote: > Hm. Are there any contexts where we'd not want the potential for failing due > to OOM? I'm not sure about this one. > I wonder if we additionally / alternatively could use a faster method of > searching the array linearly, e.g. using SIMD. I looked into using SIMD. The patch is attached, but it is only intended for benchmarking purposes and isn't anywhere close to being worth serious review. There may be a simpler/better way to implement the linear search, but this seemed to work well. Overall, SIMD provided a decent improvement. I had to increase the number of writers quite a bit in order to demonstrate where the hash tables began winning. Here are the numbers: writers head simd hash 256 663 632 694 512 530 618 637 768 489 544 573 1024 364 508 562 2048 185 306 485 4096 146 197 441 While it is unsurprising that the hash tables perform the best, there are a couple of advantages to SIMD that might make that approach worth considering. For one, there's really no overhead (i.e., you don't need to sort the array or build a hash table), so we can avoid picking an arbitrary threshold and just have one code path. Also, a SIMD implementation for a linear search through an array of integers could likely be easily reused elsewhere. > Another thing that might be worth looking into is to sort the xip/subxip > arrays into a binary-search optimized layout. That'd make the binary search > faster, wouldn't require additional memory (a boolean indicating whether > sorted somewhere, I guess), and would easily persist across copies of the > snapshot. I spent some time looking into this, but I haven't attempted to implement it. IIUC the most difficult part of this is sorting the array in place to the special layout. >> These hash tables are regarded as ephemeral; they only live in >> process-local memory and are never rewritten, copied, or >> serialized. > > What does rewriting refer to here? I mean that a hash table created for one snapshot will not be cleared and reused for another. > Not convinced that's the right idea in case of copying. I think we often end > up copying snapshots frequently, and building & allocating the hashed xids > separately every time seems not great. Right. My concern with reusing the hash tables is that we'd need to allocate much more space that would go largely unused in many cases. >> + snapshot->xiph = NULL; >> + snapshot->subxiph = NULL; > > Do we need separate hashes for these? ISTM that if we're overflowed then we > don't need ->subxip[h], and if not, then the action for an xid being in ->xip > and ->subxiph is the same? Do you mean that we can combine these into one hash table? That might work. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com

Hi Bharath, Thanks for taking a look. On Thu, Jul 14, 2022 at 03:10:56PM +0530, Bharath Rupireddy wrote: > Aren't these snapshot arrays always sorted? I see the following code: > > /* sort so we can bsearch() */ > qsort(snapshot->xip, snapshot->xcnt, sizeof(TransactionId), xidComparator); > > /* sort so we can bsearch() later */ > qsort(snap->subxip, snap->subxcnt, sizeof(TransactionId), xidComparator); AFAICT these arrays are sorted in limited cases, such as pg_current_snapshot() and logical replication. GetSnapshotData() does not appear to sort them, so I don't think we can always assume they are sorted. In the previous thread, Tomas analyzed simply sorting the arrays [0] and found that it provided much less improvement compared to the hash table approach, so I have not seriously considered it here. > If the ordering isn't an invariant of these snapshot arrays, can we > also use the hash table mechanism for all of the snapshot arrays > infrastructure rather than qsort+bsearch in a few places and hash > table for others? Unless there is demonstrable benefit in doing so for the few places that sort the arrays, I'm ѕkeptical it's worth the complexity. This patch is targeted to XidInMVCCSnapshot(), which we can demonstrate has clear impact on TPS for some workloads. > + * The current value worked well in testing, but it's still mostly a guessed-at > + * number that might need updating in the future. > + */ > +#define XIP_HASH_MIN_ELEMENTS (128) > + > > Do you see a regression with a hash table for all the cases? Why can't > we just build a hash table irrespective of these limits and use it for > all the purposes instead of making it complex with different > approaches if we don't have measurable differences in the performance > or throughput? I performed the same tests as before with a variety of values. Here are the results: writers HEAD 1 16 32 64 128 ------------------------------------ 16 659 698 678 659 665 664 32 645 661 688 657 649 663 64 659 656 653 649 663 692 128 641 636 639 679 643 716 256 619 641 619 643 653 610 512 530 609 582 602 605 702 768 469 610 608 551 571 582 1000 367 610 538 557 556 577 I was surpised to see that there really wasn't a regression at the low end, but keep in mind that this is a rather large machine and a specialized workload for generating snapshots with long [sub]xip arrays. That being said, there really wasn't any improvement at the low end, either. If we always built a hash table, we'd be introducing more overhead and memory usage in return for approximately zero benefit. My intent was to only take on the overhead in cases where we believe it might have a positive impact, which is why I picked the somewhat conservative value of 128. If the overhead isn't a concern, it might be feasible to always make [sub]xip a hash table. > +static inline bool > +XidInXip(TransactionId xid, TransactionId *xip, uint32 xcnt, > + xip_hash_hash **xiph) > > + /* Make sure the hash table is built. */ > + if (*xiph == NULL) > + { > + *xiph = xip_hash_create(TopTransactionContext, xcnt, NULL); > + > + for (int i = 0; i < xcnt; i++) > > Why create a hash table on the first search? Why can't it be built > while inserting or creating these snapshots? Basically, instead of the > array, can these snapshot structures be hash tables by themselves? I > know this requires a good amount of code refactoring, but worth > considering IMO as it removes bsearch thus might improve the > performance further. The idea is to avoid the overhead unless something actually needs to inspect these arrays. [0] https://postgr.es/m/057a9a95-19d2-05f0-17e2-f46ff20e9b3e%402ndquadrant.com -- Nathan Bossart Amazon Web Services: https://aws.amazon.com